% THIS IS SIGPROC-SP.TEX - VERSION 3.1
% WORKS WITH V3.2SP OF ACM_PROC_ARTICLE-SP.CLS
% APRIL 2009
%
% It is an example file showing how to use the 'acm_proc_article-sp.cls' V3.2SP
% LaTeX2e document class file for Conference Proceedings submissions.
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V3.2SP) *DOES NOT* produce:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) Page numbering
% ---------------------------------------------------------------------------------------------------------------
% It is an example which *does* use the .bib file (from which the .bbl file
% is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission,
% you need to 'insert'  your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% Questions regarding SIGS should be sent to
% Adrienne Griscti ---> griscti@acm.org
%
% Questions/suggestions regarding the guidelines, .tex and .cls files, etc. to
% Gerald Murray ---> murray@hq.acm.org
%
% For tracking purposes - this is V3.1SP - APRIL 2009

\documentclass{acm_proc_article-sp}
\usepackage{graphicx,epsfig}
\usepackage{setspace}
\singlespacing
\usepackage{pifont}
\usepackage{subfigure}
\usepackage{graphicx,epsfig}
\usepackage{amssymb,amsmath,bm}
\usepackage[noend]{algorithmic}
\usepackage{algorithm}
\usepackage[pdftex]{hyperref}
\usepackage{indentfirst} 
\begin{document}

\title{Energy-aware Sensors Collaboration Trajectory Tracking Framework}

%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{8} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
% You can go ahead and credit any number of authors here,
% e.g. one 'row of three' or two rows (consisting of one row of three
% and a second row of one, two or three).
%
% The command \alignauthor (no curly braces needed) should
% precede each author name, affiliation/snail-mail address and
% e-mail address. Additionally, tag each line of
% affiliation/address with \affaddr, and tag the
% e-mail address with \email.
%
% 1st. author
\alignauthor
Tianli Mo\\
       \affaddr{Univerisity of Hawaii at Manoa}\\
       \email{tianli@hawaii.edu}
% 2nd. author
\alignauthor
Alexander Cam Liu\\
       \affaddr{Univerisity of Hawaii at Manoa}\
       \email{ayj@hawaii.edu}
% 3rd. author
\alignauthor
Lipyeow Lim\\
       \affaddr{Univerisity of Hawaii at Manoa}\\
       \email{lipyeow@hawaii.edu}
}
% There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
\additionalauthors{Additional authors: John Smith (The Th{\o}rv{\"a}ld Group,
email: {\texttt{jsmith@affiliation.org}}) and Julius P.~Kumquat
(The Kumquat Consortium, email: {\texttt{jpkumquat@consortium.net}}).}
\date{30 July 1999}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle

\section{Introduction}

Many location-aware applications often keep track of trajectoies of mobile device over a long period of time, such as running paths, shared ride, habits of patients, generate maps, monitor the environmental impact and map cycling experiences.  In order to avoid drain battery too fast, the tracking has to be energy-efficient. The naive way of generating trajectory is to get GPS coordinates every certain time interval and then connect the these points to get the trajectory. However, the energy consumption of GPS is well-known high. A full power phone can die easily after perhaps 4 hours of turning on the GPS tracking. To be useful, smart strategies are needed to extend the lifetime of tracking. Hence, we propose a new framework to track the trajectory by use various sensors on mobile device including WiFi, Bluetooth and Microphone instead of only utilizing the GPS component. Also, we apply accelerometer, gyro and compass, which are all low energy cost sensor, to avoid useless position sensing. 

GPS sometimes is not able to always offer accurate current position. GPS experiences outages when phone is pockect or in "urban canyons" near tall buildings or tunnels. For exmaple if you are driving through downtown where there are many big buildings can affect GPS signal. GPS sometimes is not best choice if the mobile device has low battery power. In these case, it is better to manage other cheap ways to get the trajectory. Wifi, bluetooth, light sensor and microphone is the cheap alternative sensor can help in generating trajectory. Talbe ~\ref{tb:sensor} shows the popular sensors embeded in nowadays smart phone. The power cost vary considerablely from sensor to sensor. The table shows us the potential of saving energy because GPS is the highest energy-consumption sensor.

\begin{table}\centering
\begin{tabular}{ |l|l|l| }
  \hline
  Sensor & Power Cost & Note \\
  \hline
  Accelerometer & 0.2 &\\
  Gravity & 0.2 &\\
  Linear Accelerometer & 0.2 &\\
  Light & 0.75 &\\
  Proximity & 0.75 &\\
  Magnetic & 4 &\\
  Orientation & 4.2 &\\
  Rotation Vector & 4.2 &\\
  Bluetooth & n/a &\\
  Wifi & n/a &\\
  GPS & n/a &\\
  \hline
\end{tabular}
\caption{Sensors and their power cost}
\label{tb:sensor}
\end{table}


\begin{figure}[t]
\centering
\includegraphics[width=3.5in]{figures/map}
\caption{Example}
\label{fig:map}
\end{figure}

In Figure~\ref{fig:map} shows a map with several blocks and road segments, Alex drives a gray car in the north of Queen street and he is going back home. $O$ is the orignial position of Alex and his phone acquire the accurate coordinates by GPS at this time. Unfortunately Alex's phone only has 30\% power remain so that he decides to turn off the GPS in order to save energy. Although the GPS has been turned off, the applications or servers still want to keep track of the trajectory. After few seconds, Alex's phone detects a WiFi signal --- "\emph{Starbucks free wifi}". According to WiFi range(about 65 feet), it's reasonable to infer that Alex drives his car is passing the Starbucks. If the location of Starbucks on Dole street  is known from the map, we are able to assume that Alex is within the area $A$ meantime. Few seconds later, Alex's phone detect a bluetooth---"\emph{Tim's cellphone}". Tim happens to update his latest GPS coordinates(the strip car position) to the map. Use it as a center to draw a circle with 30 feet radius to get area $B$. Again, we can assume that Alex is passing the area $B$. Similarly, later on his phone finds McDonald's wifi singal and we infer Alex is at somewhere near McDonald's on King Street. Generally car has to follow road segments in the map otherwise it is supposed to cause accident. Therefore, a rough trajecotry, makered as dashed line in Figure~\ref{fig:map} is generated based on the three circle. 

The example above demonstrates the basic idea about using other cheap alternative sensors such as  Wifi, bluetooth, light sensor and microphone to provide information as much as possible for generating trajectory. Beside control the screen brightness, the light sensor can be used to speculate if the object enters or exits a tunnel in map. The Microphone can be used to speculate if the object enters or exits a crowed zone in map. All these sensors work collaborately to efficiently get the trajectories. A detection is a finding certain access points in the map by sensor. For example, a detection of access points can be: Wifi detect a hotspot; bluetooth finds another located object; the sound from microphone matchs a certain sound pattern of particular road segment; the light level from light sensor matchs a certain light pattern of particular road segment. The access points, hotspots, located object and particular road segment, have location information stored in map. We can generate estimated trajectory according to position samples of detection. For the example in  Figure~\ref{fig:map}, \emph{A}, \emph{B} and \emph{C} are detections which match the markers, \emph{Starbucks}, \emph{Tim} and \emph{McDonald's}. Therefore, Alex's route is supposed to contain the road segments which intersect with area \emph{A}, \emph{B} and \emph{C}.



However, these sensors detections unfortunately cannot provide 100\% accurate location: if a Wifi hotspot has been moved to new location but the map has not been updated and still store the old location of it; a bluetooth detection is inaccurate if that object has inaccurate location of itself; light pattern detections and sound pattern detections are just estimates without accuracy guarantee. Hence, to cope with this face, we give each kind of detection a \emph{reliability}. The \emph{reliability} aims to measure how much we can trust a detection. GPS has the highest reliability because it usually provide the most accurate position than other sensors, but it has to depend on the specific situation. Wifi has the second and bluetooth comes next. The reliability of  microphone and light is the relatively small due to their limitation. When generate a trajectory, the \emph{reliability} need to be taken into account. If there are more than one path candidates, and only one path can be choosed to be trajectory, we choose the path with the highest total \emph{reliability}. 

For some scenarios, the system collections trajectories of objects daily or periodly. Therefore there are available history trajectories which can be reused when generate current trajectory. For example, if there are two path candidates with same\emph{reliability}. According to the history trajectories, the object passed through path A more times than passed through path B, so we choose the path A to be trajectory. For a particular object, each road segment has a \emph{weight} based on how many times the object passed through it before. In path candidates, a path with higher total \emph{weight} should get higher probability of being choosed as trajectory. 

The algorithm to generate trajectory by total weight of path is as follows:


 In this project, we try to use Hidden Markov Model and Viterbi algorithm to determine the highest probability route to be the trajectory. While the output (list of detections) is known, the sequence of states is not; the problem is to determine the most likely sequence of states that produced the output.

We can use accelerometer, gyro and compass to further save energy cost. If a car moves along a road segment and the acceleration is negligiblely small and the direction does not change, we conjecture the car will keep the current movement status and follow the same road segment without making turn. Therefore, location sensing in a certain time is waste because the trajectory can be predicted by the previous movement status. Less sensings are requested mean less energy comsuption.   

\section{Implementation}

\begin{table}\centering
\begin{tabular}{ |l|l|}
  \hline
  Phone & Samsung Exhibit I \\
  \hline
  Android OS & 2.3 (GingerBread) \\
  \hline
  Processor & Single core, 1000 MHz, ARM Cortex-A8 \\
  \hline
  RAM & 512 MB \\
  \hline
  Battery Capacity & 1500 mAh \\
  \hline
\end{tabular}
\caption{Phone hardware specs}
\label{tb:hardware}
\end{table}

The implementation would be done using the Android mobile OS (Java). It will take advantages of various APIs available such as:

\begin{enumerate}

\item Google Maps API.
\item The embedded sensors API (only available sensors from the phone).

	\begin{enumerate}
	
	\item Accelerometer.
	\item Gyroscope.
	\item Microphone, etc.
	
	\end{enumerate}

\item Connectivity Network API.


	\begin{enumerate}
	
	\item GPS.
	\item Network (WIFI, 3G).
	\item Bluetooth.
	
	\end{enumerate}

\end{enumerate}

For implementing our approach, a app running on Android phone will be created. The app selectively  runs on two modes, \emph{normal} and \emph{saving}. The \emph{normal} mode employs the GPS sensor to generate the trajectory, usually for when the GPS is available and the battery is full charge. The  \emph{saving} mode employs our approach to get the approximate trajectory in energy-efficiency way. We will compare the energy consumptions of these two mode to show the how much energy our approach can save during a certain period of time.

The basic idea of the implementation is, first, get the latest location of a user as a starting point on \emph{normal} mode. Then the app will  switch to \emph{saving} mode. The app will detect if the user is walking/driving on a straight line, meaning minimum amount of acceleration change, and no change of direction. As explained above, this is done by using sensors such as accelerometer, gyroscope, and compass which are the cheapest sensors. Afterwards, the choosing of the next sensors to be used will be based on an algorithm that still is been working on to be implemented. 

The testing of the implementation will be done using the University of Hawaii at Manoa campus area as it has a good number of WIFI hotspots installed in most of the buildings across campus. However, due to a policy of the Information Technology Department at Manoa (ITS), all WIFI hotspots has the same SSID name: 'UHM'. This lead to the problem of finding the right location of the WIFI detected by the app. After some research of the UHM area, we had identified an unique id of each the UHM wireless hotspots: \em BSSID. \em The \em BSSID \em is the MAC address of the Wireless Access Point. Therefore, we can create a database of the location of all the UHM Wireless hotspots with its \em BSSID \em to be used for a lookup when the app detects a WIFI hotspot on campus. 

After collecting all the \em BSSIDs \em, we would then have our custom Google Maps with all the WIFI locations pointed on the map. It will used also as a result to show the predicted trajectory of the user when the app stops running. 

For the Bluetooth strategy, we have another Andriod phone(access point) installed a simple app that can transfer its current location to test phone by bluetooth. Due to the limited time, the sound and light pattern is out of the paper's scope.
\end{document}
